#include "common.h"

int subarraysDivByK(vector<int>& nums, int k)
{
	int n = nums.size();
	map<int, int> record({ { 0,1 } });
	int ans = 0;
	int sum = 0;
	for (auto num : nums)
	{
		sum += num;
		int m = (sum % k + k) % k;
		if (record.count(m))
			ans += record[m];
		record[m]++;
	}
	return ans;
}